3sum smaller¶
Time: O(N^2); Space: O(1); medium
Given an array of n integers nums and a target, find the number of index triplets
(i, j, k) with 0 <= i < j < k < n
that satisfy the condition:
nums[i] + nums[j] + nums[k] < target.
Example 1:
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation:
Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Example 2:
Input: nums = [-2,0,-1,3], target = 2
Output: 3
Explanation:
Because there are three triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
[-2, -1, 3]
Challenge:
Could you solve it in O(N^2) runtime?
[1]:
class Solution1(object):
"""
Time: O(N^2)
Space: O(1)
"""
def threeSumSmaller(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
n = len(nums)
count, k = 0, 2
while k < n:
i, j = 0, k - 1
while i < j: # Two Pointers, linear time.
if nums[i] + nums[j] + nums[k] >= target:
j -= 1
else:
count += j - i
i += 1
k += 1
return count
[2]:
s = Solution1()
nums = [-2,0,1,3]
target = 2
assert s.threeSumSmaller(nums, target) == 2
nums = [-2,0,-1,3]
target = 2
assert s.threeSumSmaller(nums, target) == 3